function arrData(num){
    for (let i = 0; i < num; i++){
        arr[i] = Math.floor(Math.random() * num + 1)
    }
}


function qSort(myArr){
    if(myArr.length === 0){
        return []
    }

    let smallArr = []
    let bigArr = []
    let pivot = myArr[0]
    for (let i = 1; i < myArr.length; i++){
        if (myArr[i] < pivot){
            smallArr.push(myArr[i])
        } else {
            bigArr.push(myArr[i])
        }
    }
    // return qSort(smallArr).concat(pivot, qSort(bigArr))
    return [...qSort(smallArr), pivot, ...qSort(bigArr)]
}
function qqSort(myArr){
    if (myArr.length === 0){
        return []
    }

    let left = []
    let right = []
    let index = Math.floor(myArr.length / 2)
    let pivot = myArr.splice(index, 1)[0]

    for (let i = 0; i < myArr.length; i++){
        if (myArr[i] <= pivot){
            left.push(myArr[i])
        } else {
            right.push(myArr[i])
        }
    }

    return [...qqSort(left), pivot, ...qqSort(right)];
}


function jsSort(myArr){
    for(let i = 0; i < myArr.length - 1; i++){
        for(let j = 0; j < myArr.length - 1; j++){
            if (myArr[j] > myArr[j + 1]){
                [myArr[j], myArr[j + 1]] = [myArr[j + 1], myArr[j]]
            }
        }
    }

    return myArr
}


function selectSort(myArr){
    let minIndex, temp;
    var len = myArr.length
    for(let i = 0; i < myArr.length; i++){
        minIndex = i
        for (let j = i + 1; j < myArr.length; j++){
            if (myArr[j] < myArr[minIndex]){
               minIndex = j
            }
        }
        [myArr[i], myArr[minIndex]] = [myArr[minIndex], myArr[i]]
    }

    return myArr
}


function insertSort(myArr){
    let temp, j;
    for (let i = 1; i < myArr.length; i++){
        temp = myArr[i]
        j = i
        while (j > 0 && myArr[j - 1] > temp) {
            myArr[j] = myArr[j - 1]
            j--
        }
        myArr[j] = temp;
    }

    return myArr
}

let arr = []
arrData(100)

// console.time('end js order')
// arr = jsSort(arr)
// console.timeEnd('end js order')

// console.time('end select order')
// arr = selectSort(arr)
// console.timeEnd('end select order')

// console.time('end insert order')
// arr = insertSort(arr)
// console.timeEnd('end insert order')

// console.time(`start quick order`)
// arr = qSort(arr)
// console.timeEnd(`start quick order`)
